// =====================================================================================
// 
//       Filename:  routes.cpp
// 
//    Description:  Implémentation du module de gestion du réseau routier et des procédures
//    				d'importation depuis le format MID/MIF
// 
//        Version:  1.0
//        Created:  06/07/2009 21:50:31
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:  
// 
// =====================================================================================

#include	<vector>
#include	<list>
#include	<deque>
#include	<fstream>
#include	<string>
#include	<sstream>
#include	<algorithm>
#include	<cfloat>
#include	<cmath>
#include	<cctype>
#include	"parser.h"
#include	"erreurs.h"
#include	"config.h"
#include	"ast.h"
#include	"kdtree.h"
#include	"geometrie.h"
#include	"graphe.h"
#include	"gisobjects.h"
#include	"routes.h"

using namespace std;

/**********************************************/
/* FONCTIONS DIVERSES UTILISEES PAR LE MODULE */
/**********************************************/
/**
 * \fn bool point_compare(const Point *p1,const Point *p2)
 * \brief Compare deux points en tenant compte de leurs abscisses et de leurs ordonnées respectives
 *
 * La fonction compare les points \f$P_1(x_1,y_1)\f$ et \f$P_2(x_2,y_2)\f$ selon une relation d'ordre totale sur l'espace définie par :
 * \f$ P_1\leq P_2 \Leftrightarrow \left\{\begin{array}{l} x_1\leq x_2 \\ \hbox{si }x_1=x_2\hbox{,}y_1\leq y_2 \\ \end{array}\right.\f$
 * et
 * \f$ P_1=P_2 P_2 \Leftrightarrow \left\{\begin{array}{l} x_1=x_2 \\ y_1=y_2 \\ \end{array}\right.\f$
 * La fonction est utilisée pour le tri de la liste temporaire des sommets lors de l'importation d'un fichier MapInfo MIF/MID.
 * \param p1 Premier point à comparer
 * \param p2 Second point à comparer
 * \return true si \f$P_1<P_2\f$, false sinon
 */
bool point_compare(const Point *p1,const Point *p2) {
	return (*p1)<(*p2);
}

void coordonnees(const void* point,double* coords) {
	((const Intersection*)(point))->coordonnees(coords);
}

double carre_distance(const void *point,const double *ppoint) {
	return ((const Intersection*)(point))->carre_distance(ppoint[0],ppoint[1]);
}

bool true_condition_i(const Intersection *p) {return true;}

/**
 * \fn AST::Value valeur_variable(const string &nom,const void* enr)
 * \brief Fonction de recherche de la valeur de la variable nom dans l'enregistrement enr
 *
 * La fonction recherche la valeur dont le nom est spécifié dans l'enregistrement enr. Elle est utilisée comme interface d'accès à une structure de données attributaires lors de l'évaluation d'un arbre syntaxique par la méthode AST::SyntaxNode::get_value(). Cette dernière méthode prend en argument une fonction de recherche d'une variable dans la base de données, et un pointeur sans type qui peut représenter un enregistrement. Cette méthode permet d'assurer la bonne modularité du système : les arbres de syntaxe abtraite sont traités entièrement dans le module ast.h, les données attributaires sont gérées entièrement dans le module attributs.h, et cette fonction assure le lien entre les deux.
 * \param nom Nom de la variable à rechercher
 * \param enr Pointeur vers la structure de données où doit être recherchée la variable. Dans le cas présent, il s'agit de l'enregistrement du tronçon de route examiné.
 * \return Valeur de la variable
 */
AST::Value valeur_variable(const string &nom,const void *enr) {
	// Définition de quelques valeurs supplémentaires utilisables par les applications
	Troncon *e=((Troncon*)enr);
	if (string_compare(nom,"_length")) return e->longueur();
	// Recherche d'un champ dans l'enregistrement
	const DescriptionTable *dt=e->get_dt();	// Table de description des champs de l'enregistrement enr
	int id=dt->get_index(nom);	// Index du champ dans la table de description des champs de l'enregistrement enr
	if (id==-1) return AST::Value();	// Le champ n'a pas été trouvé
	Champ ch=dt->champ(id);	// Champ correspondant à la variable nom
	switch (ch.type) {
		case Champ::ENTIER:return AST::Value(e->get_int(id));
		case Champ::ENTIER_LONG:return AST::Value((int)(e->get_long(id)));
		case Champ::FLOTTANT:return AST::Value((double)(e->get_float(id)));
		case Champ::DOUBLE:return AST::Value(e->get_double(id));
		case Champ::CHAINE:return AST::Value(e->get_string(id));
		default:return AST::Value();
	}
}

/***************************************/
/* IMPLEMENTATION DE LA CLASSE TRONCON */
/***************************************/
void Troncon::affiche(ostream& out) const {
	//out << id << "," << get_string("NUMERO") << "," << get_string("NOM_RUE_G") << "," << get_string("SENS") << "," << poids << "u";
	out << id << "," << poids << "u";
}

bool Troncon::lecture(ifstream &mif,ifstream &mid,char sep) throw (IOException,ParseException) {
	const string types[] = {"line","pline"};
	vide();
	// Lecture des caractéristiques géométriques du tronçon
	if (mif.eof()) return false;
	string line;
	int num_type;	//Numéro du type du nouvel élément
	do {
		getline(mif,line);
		line=trim(line);
		num_type=-1;
		int i=0;
		while (num_type<0 && i<2 && !string_compare(types[i],line,0,types[i].length())) ++i;
		if (i<2) num_type=i;
	} while (!mif.eof() && num_type<0);
	if (mif.eof()) return false;
	// La ligne qui commence par "Pline" a pour format "Pline xx" avec xx le nombre de sommets à lire.
	// La ligne qui commence par "Line" a pour format "Line xa ya xb yb" avec (xa,ya) et (xb,yb) les coordonnées des deux extrémités de la ligne.
	// Les coordonnées de chaque sommet suivent, avec un sommet par ligne soit deux réels.
	// La description du polygone se termine éventuellement par une ligne contenant "    Pen (xx,xx,xx)" où les paramètres sont les attributs du tracé
	if (num_type==0) {
		double xa,ya,xb,yb;
		istringstream iss(line.substr(5));
		iss >> xa >> ya >> xb >> yb;
		ajoute_point(new Point(xa,ya));
		ajoute_point(new Point(xb,yb));
		if (xa<parent->xmin) parent->xmin=xa;if (xb<parent->xmin) parent->xmin=xb;
		if (ya<parent->ymin) parent->ymin=ya;if (yb<parent->ymin) parent->ymin=yb;

	}
	if (num_type==1) {
		double x,y;
		istringstream iss;
		if (line.length()>5) iss.str(line.substr(6)); else {
			getline(mif,line);
			iss.str(trim(line));
		}
		int nb_sommets;
		iss >> nb_sommets;

		for (int i=0;i<nb_sommets;++i) {
			getline(mif,line);
			istringstream iss2(line);
			iss2 >> x >> y;
			// Ajustement des frontières du domaine
			if (x<parent->xmin) parent->xmin=x;
			if (x>parent->xmax) parent->xmax=x;
			if (y<parent->ymin) parent->ymin=y;
			if (y>parent->ymax) parent->ymax=y;
			ajoute_point(new Point(x,y));
		}
	}
	// Lecture des attributs du tronçon
	getline(mid,line);
	size_t pos=0;	// Position courante de lecture dans la chaîne de caractères
	for (int i=0;i<description->nombre();++i) {
		if (description->champ(i).type==Champ::ENTIER)
			set(i,getint(line,pos,sep));
		else if (description->champ(i).type==Champ::DOUBLE)
		   	set(i,getfloat(line,pos,sep));
		else if (description->champ(i).type==Champ::CHAINE)
		   	set(i,getstring(line,pos,sep));
	}

	return true;
}

double Troncon::calcule_poids(AST::SyntaxNode *arbre) const {
	if (!arbre) return longueur()/vitesse;
	return arbre->get_value(valeur_variable,this).get_double();
}

/**************************************/
/* IMPLEMENTATION DE LA CLASSE RESEAU */
/**************************************/
Reseau::~Reseau() {
	vide();
	delete description;
	delete arbre;
}

vector<Intersection*> Reseau::intersections() const {
	vector<Intersection*> res(sommets.size());
	vector<Sommet*>::const_iterator it=sommets.begin();
	vector<Intersection*>::iterator it2=res.begin();
	while (it!=sommets.end()) {
		*it2=(Intersection*)(*it);
		it++;
		it2++;
	}
	return res;
}

void Reseau::init_couleurs() {
	for (vector<Arc*>::iterator it=arcs.begin();it!=arcs.end();it++) ((Troncon*)(*it))->tag=0;
}

double Reseau::projection_simple(double x,double y,Intersection *&noeud,bool (*condition)(const Intersection*)) const {
	// Recherche du sommet le plus proche dans le réseau
	noeud=0;
	double dmin=DBL_MAX;
	double d,a,b;
	for (vector<Sommet*>::const_iterator it=sommets.begin();it!=sommets.end();it++) if (condition((Intersection*)(*it))) {
		a=((Intersection*)(*it))->x-x;
		b=((Intersection*)(*it))->y-y;
		d=a*a+b*b;
		if (d<dmin) {
			dmin=d;
			noeud=(Intersection*)(*it);
		}
	}
	if (noeud==0) return -1;
	return sqrt(dmin);
}

double Reseau::projection(double x,double y,Intersection *&noeud,bool (*condition)(const Intersection*)) {
	if (!arbre) arbre=new Kd_tree<2,Intersection,coordonnees,carre_distance>(intersections());
	double carre_dist;
	double ppoint[2]={x,y};
	noeud=arbre->neighbour(ppoint,carre_dist,condition);
	if (noeud==0) return -1;
	return sqrt(carre_dist);
}

Intersection* Reseau::cherchep(const Point &p) const {
	int a=0;
	int b=sommets.size()-1;
	int c;
	if (b<a || p<*((Point*)((Intersection*)(sommets[a]))) || *((Point*)((Intersection*)(sommets[b])))<p) return 0;
	while (b>a+1) {
		if (*((Point* const)((Intersection* const)(sommets[a])))==p) return (Intersection*)sommets[a];
		if (*((Point* const)((Intersection* const)(sommets[b])))==p) return (Intersection*)sommets[b];
		c=(a+b)/2;
		if (p<*((Point* const)((Intersection* const)(sommets[c])))) b=c; else a=c;
	}
	if (*((Point* const)((Intersection* const)(sommets[a])))==p) return (Intersection*)sommets[a];
	if (*((Point* const)((Intersection* const)(sommets[b])))==p) return (Intersection*)sommets[b];
	return 0;
}

void Reseau::importe_mid_mif(const string &mif,const string &mid,Config &conf) {
	// Ouverture des fichiers en lecture et activation de la gestion des exceptions pour éviter les erreurs de format de fichiers
	ifstream ifs1(mid.c_str(),ifstream::in);
	ifstream ifs2(mif.c_str(),ifstream::in);
	if ((!ifs1.is_open())||(ifs1.eof())) throw IOException(IOException::FILE_NOT_FOUND,mid);
	if ((!ifs2.is_open())||(ifs2.eof())) throw IOException(IOException::FILE_NOT_FOUND,mif);
	ifs1.exceptions(ifstream::badbit);
	ifs2.exceptions(ifstream::badbit);
	// Lecture du nombre de colonnes (nombre d'attributs)
	int nb_colonnes;
	char sep;
	bool stop=false;
	string line;
	sep='\t';
	while (!stop && !ifs2.eof()) {
		getline(ifs2,line);
		if (string_compare("Delimiter",line,0,9)) sep=line[11];
		else if (string_compare("Columns",line,0,7)) stop=true;
	}
	istringstream iss1(line.substr(8));
	iss1 >> nb_colonnes;
	// Lecture des attributs et création de la structure DescriptionTable
	if (description) delete description;
	description=new DescriptionTable(nb_colonnes);
	for (int i=0;i<nb_colonnes;++i) {
		getline(ifs2,line);
		size_t j=0;
		while (j<line.length() && isspace(line[j])) ++j;
		size_t k=j;
		while (k<line.length() && !isspace(line[k])) ++k;
		string nom_col=line.substr(j,k-j);
		while (k<line.length() && isspace(line[k])) ++k;
		if (string_compare("integer",line,k,7)) description->ajoute_champ(Champ(Champ::ENTIER,nom_col));
		else if (string_compare("decimal",line,k,7)) description->ajoute_champ(Champ(Champ::DOUBLE,nom_col));
		else if (string_compare("char",line,k,4)) description->ajoute_champ(Champ(Champ::CHAINE,nom_col));
		else if (string_compare("float",line,k,4)) description->ajoute_champ(Champ(Champ::DOUBLE,nom_col));
		else description->ajoute_champ(Champ(Champ::NUL,nom_col));
	}
	// Recherche des index des champs importants
	conf.champ_sens=description->get_index(conf.nom_sens);
	if (conf.champ_sens<0 || description->champ(conf.champ_sens).type!=Champ::CHAINE) {	// On se limite à la comparaison de chaînes de caractères
		conf.champ_sens=-1;
		cerr << "Champ Sens introuvable\n";
	}
	conf.champ_zini=description->get_index(conf.nom_zini);
	if (conf.champ_zini<0 || description->champ(conf.champ_zini).type!=Champ::DOUBLE) {	// Le champ doit être de type double
		conf.champ_zini=-1;
		cerr << "Champ Z_Ini introuvable\n";
	}
	conf.champ_zfin=description->get_index(conf.nom_zfin);
	if (conf.champ_zfin<0 || description->champ(conf.champ_zfin).type!=Champ::DOUBLE) {	// Le champ doit être de type double
		conf.champ_zfin=-1;
		cerr << "Champ Z_Fin introuvable\n";
	}
	// Déplacement au début de la section relative aux données géographiques
	stop=false;
	while (!stop && !ifs2.eof()) {
		getline(ifs2,line);
		if (string_compare("data",line,0,4)) stop=true;
	}
	// Initialisation des frontières du domaine
	xmin=DBL_MAX;
	xmax=-DBL_MAX;
	ymin=DBL_MAX;
	ymax=-DBL_MAX;
	// Autres initialisations
	vector<Point*> tmp_sommets;	// Liste temporaire pour le stockage des sommets
	// Boucle principale de lecture des fichiers
	bool fini=false;
	int arc_index=1;

	while (!fini) {
		// Lecture du tronçon
		Troncon *t=new Troncon(this,description);
		if (!t->lecture(ifs2,ifs1,sep)) {
			fini=true;
			delete t;
			continue;
		}
		t->poids=t->calcule_poids(conf.poids);
		// Ajout des sommets à la liste temporaire
		tmp_sommets.push_back(t->front());
		tmp_sommets.push_back(t->back());
		// Ajout des tronçons au réseau, en tenant compte des sens de circulation
		if (conf.champ_sens>=0) {
			string sens_val=t->get_string(conf.champ_sens);
			if (sens_val.compare(conf.sens_inverse)==0) {	// Si le sens de circulation réel est le sens opposé à celui de la définition, on échange les sommets initial et final
				reverse(t->begin(),t->end());
			}
			else if (sens_val.compare(conf.sens_unique)!=0) {	// Si le sens de circulation réel est double, on crée un autre tronçon identique au premier mais dont les sommets initial et final sont échangés et on l'ajoute à la liste. Par défaut, si le sens de circulation n'est pas connu (ni direct, ni indirect, ni double), on considère que la voie est double.
				Troncon *ti=new Troncon(*t);
				reverse(ti->begin(),ti->end());
				arcs.push_back(ti);
				ti->id=arc_index++;
			}
		} else {
			Troncon *ti=new Troncon(*t);
			reverse(ti->begin(),ti->end());
			arcs.push_back(ti);
			ti->id=arc_index++;
		}
		arcs.push_back(t);
		t->id=arc_index++;
	}


	// Fermeture des fichiers
	ifs1.close();
	ifs2.close();
	// Construction de la liste des sommets
	sort(tmp_sommets.begin(),tmp_sommets.end(),point_compare);
	double lastx=-1.0;
	double lasty=-1.0; // Anciens identifiants de sommet, permettent de détecter les doublons
	int num_sommet=1;	// Index unique pour définir le sommet et faciliter les recherches dans la liste
	for (vector<Point*>::iterator it=tmp_sommets.begin();it!=tmp_sommets.end();it++) {
		if ((*it)->x!=lastx || (*it)->y!=lasty) {
			sommets.push_back(new Intersection(num_sommet,"",(*it)->x,(*it)->y));
			num_sommet++;
			lastx=(*it)->x;
			lasty=(*it)->y;
		}
	} // Ici la liste de sommets contient une fois chaque sommet et est triée dans l'ordre croissant de leurs identifiants par construction
 	// Association des tronçons à leurs sommets
	for (vector<Arc*>::iterator it=arcs.begin();it!=arcs.end();it++) {
		Intersection *ss=cherchep(*(((Troncon*)(*it))->front()));
		(*it)->orig=ss;
		ss->arcs.push_back(*it);
		ss=cherchep(*(((Troncon*)(*it))->back()));
		(*it)->dest=ss;
	}
}

/**********************************************/
/*  IMPLEMENTATION DES OPERATEURS D'AFFICHAGE */
/**********************************************/
ostream& operator<< (ostream& out,const Point &p) {
	p.affiche(out);
	return out;
}

ostream& operator<< (ostream& out,const Polyligne &pl) {
	pl.affiche(out);
	return out;
}

ostream& operator<< (ostream &out, const Reseau &r) {
	out << "Réseau - " << r.sommets.size() << " noeuds, " << r.arcs.size() << " tronçons - (" << r.xmin << "," << r.ymin << ") à (" << r.xmax << "," << r.ymax << ")" << endl;
	return out;
}
